#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

struct Edge {
	int to;
	int weight;
};

vector<int> Dijkstra(vector<vector<Edge>>& graph, int start) {
	int n = graph.size();
	vector<int> dist(n, INF);
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;
	
	while (!pq.empty()) {
		int d = pq.top().first;
		int u = pq.top().second;
		pq.pop();
		
		if (d > dist[u]) {
			continue;
		}
		
		for (const Edge& edge : graph[u]) {
			int v = edge.to;
			int weight = edge.weight;
			if (dist[u] + weight < dist[v]) {
				dist[v] = dist[u] + weight;
				pq.push(make_pair(dist[v], v));
			}
		}
	}
	
	return dist;
}

int main() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<Edge>> graph(n+1);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}
	
	vector<int> dist = Dijkstra(graph, 1);
	
	cout << dist[n] << endl;
	
	return 0;
}

